package com.sise.Linked;

/**
 *      剑指 Offer 25. 合并两个排序的链表
 *
 *      输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
 *
 *      示例1：
 *      输入：1->2->4, 1->3->4
 *      输出：1->1->2->3->4->4
 *
 *      题解1：
 *          设置一个哑结点，逐一比较 双链表的头结点，将其设置在哑结点的下一位置。
 */
public class _offer_25_mergeTwoLists {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode dumHead = new ListNode(0); // 哑结点
        ListNode cur = dumHead;

        while (l1 != null && l2 != null) {      // 当其中两条链路都不为空时，那么就进行值判断
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;                     // 结果链路往后推一步
        }

        cur.next = (l1 != null ? l1 : l2);      // 能到这一步，说明 while 循环已经结束了，只需要拼接剩下的 l1 或 l2 链路即可
        return dumHead.next;
    }


    /**
     *      递归
     *      1、终止条件：当有一条链表为空，那么就直接返回另外一条链表作为尾部
     *      2、找返回值：返回已经排好序的链表
     *      3、本次递归：找出哪条链表的数值更小，这里采用的是新建 head 节点，然后将较小值赋给它，这样子不会破坏原有链表的结构
     */
    public ListNode mergeTwoLists_2(ListNode l1, ListNode l2) {
        //递归实现
        return recur(l1, l2);
    }

    public ListNode recur(ListNode l1, ListNode l2){
        //是否为null判断
        if(l1 == null && l2 == null) return null;
        if(l1 == null) return l2;
        if(l2 == null) return l1;

        //新建头结点
        ListNode head = null;

        //如果 l1.val <= l2.val，那么头结点的值为 l1.head 的值，然后开始递归
        if(l1.val <= l2.val){
            head = new ListNode(l1.val);
            head.next = recur(l1.next, l2);
        }
        //否则，头结点的值为l2.head的值，然后开始递归
        else{
            head = new ListNode(l2.val);
            head.next = recur(l1, l2.next);
        }

        //返回该链表
        return head;
    }
}

